#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct node {
  ElemType date;
  struct node *next;
} Node;

// 单链表 - 初始化
Node *initList() {
  Node *head = (Node *)malloc(sizeof(Node));
  head->date = 0;
  head->next = NULL;
  return head;
}

// 单链表 - 头插法
void insertHead(Node *L, ElemType e) {
  Node *p = (Node *)malloc(sizeof(Node));
  p->date = e;
  p->next = L->next;
  L->next = p;
}

// 单链表 - 尾插法
// 获取尾节点
Node *get_tail(Node *L) {
  Node *p = L;
  while (p->next != NULL) {
    p = p->next;
  }
  return p;
}
// 将数据插入尾部
Node *insertTail(Node *tail, ElemType e) {
  Node *p = (Node *)malloc(sizeof(Node));
  p->date = e;
  tail->next = p;
  p->next = NULL;
  return p;
}

// 单链表 - 在指定位置插入
int insertNode(Node *L, int pos, ElemType e) {
  Node *p = L;
  int i = 0;
  while (i < pos - 1) {
    p = p->next;
    i++;
    if (p == NULL) {
      return 0;
    }
  }
  Node *q = (Node *)malloc(sizeof(Node));
  q->date = e;
  q->next = p->next;
  p->next = q;
}

// 单链表 - 删除节点
int deleteNode(Node *L, int pos) {
  // 找到被删除节点的前驱节点
  Node *p = L;
  int i = 0;
  while (i < pos - 1) {
    p = p->next;
    i++;
    if (p == NULL) {
      return 0;
    }
  }
  if (p->next == NULL) {
    printf("要删除的位置错误\n");
    return 0;
  }
  // q指向被删除的节点
  Node *q = p->next;
  // 前驱节点指向指向被删除节点的next
  p->next = q->next;
  free(q);
  return 1;
}

// 单链表 - 遍历
void listNode(Node *L) {
  Node *p = L->next;
  while (p != NULL) {
    printf("%d ", p->date);
    p = p->next;
  }
  printf("\n");
}

// 单链表 - 获取链表长度
int listLength(Node *L) {
  Node *p = L;
  int len = 0;
  while (p != NULL) {
    p = p->next;
    len++;
  }
  return len;
}

// 单链表 - 释放链表
void freeNode(Node *L) {
  Node *p = L->next;
  Node *q;
  while (p != NULL) {
    q = p->next;
    free(p);
    p = q;
  }
  L->next = NULL;
}

// 查找倒数第k个节点
int findNodeFS(Node *L, int k) {
  Node *fast = L->next;
  Node *slow = L->next;
  for (int i = 0; i < k; i++) {
    fast = fast->next;
  }
  while (fast != NULL) {
    fast = fast->next;
    slow = slow->next;
  }
  printf("倒数第%d个节点的内容为:%d\n", k, slow->date);
  return 1;
}

// 删除链表中绝对值相同的节点
void removeNode(Node* L,int n)
{
  Node* p = L;
  int index;
  int* q = (int*)malloc(sizeof(int)*(n+1));

  for(int i = 0;i < n + 1;i++)
    *(q + i) = 0;
  while(p->next != NULL)
  {
    index = abs(p->next->date);
    if(*(q+index) == 0)
    {
      *(q+index) = 1;
      p=p->next;
    }
    else
    {
      Node* temp = p->next;
      p->next = temp->next;
      free(temp);
    }
  }
  free(q);
}

//反转链表
  Node* reverseList(Node* head)
  {
    Node* first = NULL;
    Node* second = head->next;
    Node* third;
    while(second != NULL)
    {
      third = second->next;
      second->next = first;
      first = second;
      second = third;
    }
    Node* hd = initList();
    hd->next = first;
    return hd;
  }

//单链表应用-删除中间节点
  int delMiddleNode(Node* head)
  {
    Node* fast = head->next;
    Node* slow = head;
    while(fast != NULL && fast->next != NULL)
    {
      fast = fast->next->next;
      slow = slow->next;
    }
    Node* q = slow->next;
    slow->next = q->next;
    free(q);
    return 1;
  }

//链表重新排序
  

int main(int argc, char const *argv[]) {
  Node *list = initList();
  insertHead(list, 10);
  insertHead(list, 11);
  insertHead(list, 12);
  listNode(list);
  Node *tail = get_tail(list);
  tail = insertTail(tail, 13);
  tail = insertTail(tail, 14);
  tail = insertTail(tail, 15);
  tail = insertTail(tail, -15);

  listNode(list);
  insertNode(list, 5, 20);
  listNode(list);
  deleteNode(list, 5);
  listNode(list);
  printf("链表的长度为(包括头节点):%d\n", listLength(list));
  findNodeFS(list, 3);
  removeNode(list, 15);
  listNode(list);
  delMiddleNode(list);//单链表应用-删除中间节点
  listNode(list);
  Node* reverse = reverseList(list);//反转链表
  listNode(reverse);
  freeNode(list);
  printf("内存释放后的链表的长度为(包括头节点):%d\n", listLength(list));

  return 1;
}